public class Solution21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p = list1, q = list2;
        ListNode t = new ListNode();
        ListNode res = t;

        while (p != null && q != null) {
            if (p.val <= q.val) {
                t.next = p;
                p = p.next;
            } else {
                t.next = q;
                q = q.next;
            }
            t = t.next;
        }

        if (p == null) {
            t.next = q;
        } else {
            t.next = p;
        }
        res = res.next;

        return res;
    }
}
